package 代码随想录.动态规划.a;

public class a343整数拆分 {
    static class Solution {
        public int integerBreak(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 0;
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
                for (int j = 1; j <= i / 2; j++) {
                    int cur = Math.max(j * (i - j), j * dp[i - j]);
                    dp[i] = Math.max(dp[i], cur);
                }
            }
            return dp[n];
        }
    }

    static class Solution2 {
        public int max = 1;

        public int integerBreak(int n) {
            if (n == 2 || n == 3) {
                return n - 1;
            }
            backTracking(n, 1, 1);
            return max;
        }

        private void backTracking(int n, int start, int mul) {
            if (n <= 1 || start > n) {
                max = Math.max(mul, max);
            }
            for (int i = start; i <= n; i++) {
                mul *= i;
                backTracking(n - i, i, mul);
                mul /= i;
            }
        }
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int n = 4;
        System.out.println(solution.integerBreak(n));
    }
}
